package org.example.SolutionNew001;

public class Matrix04 {
    public static void main(String[] args) {
        Matrix04 matrix = new Matrix04();
        int[][] m=new int[][]{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        System.out.println(matrix.searchMatrix(m,20));

    }

    public boolean searchMatrix1(int[][] matrix, int target) {
        boolean res=false;
        int m = matrix.length,n = matrix[0].length;
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(matrix[i][j]==target) {
                    res=true;
                }
            }
        }
        return res;
    }

    //二分查找(优化上一个一个个遍历的思想)
    public boolean searchMatrix2(int[][] matrix, int target) {
        boolean res=false;
        int m = matrix.length,n = matrix[0].length;
        for(int i=0; i<m; i++) {
            if (judgeThisFloor(matrix[i],target)){
                res = true;
                break;
            }
        }
        return res;
    }

    public boolean judgeThisFloor(int[] matrix, int target) {
        int n=matrix.length;
        int start=0,end=n-1;
        while(start<=end) {
            int mid=start+(end-start)/2;
            if(matrix[mid]==target) {
                return true;
            }else if(matrix[mid]>target) {
                end=mid-1;
            }else{
                start=mid+1;
            }
        }
        return false;
    }

    //排除一行或一列的Z字法
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length,n = matrix[0].length;
        int x=0,y=n-1;
        while(x<m && y>=0) {
            if(matrix[x][y]==target) {
                return true;
            }else if(matrix[x][y]>target) {
                y--;
            }else{
                x++;
            }
        }
        return false;
    }
}
